#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


# class Solution:
#     """
#     @param nums: A list of integers
#     @return: An integer indicate the value of maximum difference between two substrings
#     """
#     def maxDiffSubArrays(self, nums):
#         # write your code here
#         pass


class Solution:
    def maxDiffSubArrays(self, nums):
        self.n = len(nums)
        self.nums = nums
        self.ret = 0
        self.init_data()

        self.make_forward()
        self.make_reverse()
        return  self.tow_max()

    def init_data(self):
        self.forward_local_max = [None] * self.n      # 以i结尾的数组的最大值
        self.forward_global_max = [None] * self.n      # 0---->i 之间 某连续数组的最大值, 不一定以i结尾
        self.inverse_local_max = [None] * self.n      # 以i结尾的反向数组的最大值
        self.inverse_global_max = [None] * self.n      # end--->i 之间 某连续数组的最大值, 不一定以i结尾, 总之最大

        self.forward_local_min = [None] * self.n      # 以i结尾的数组的最大值
        self.forward_global_min = [None] * self.n      # 0---->i 之间 某连续数组的最大值, 不一定以i结尾
        self.inverse_local_min = [None] * self.n      # 以i结尾的反向数组的最大值
        self.inverse_global_min = [None] * self.n      # end--->i 之间 某连续数组的最大值, 不一定以i结尾, 总之最大

    def make_forward(self):
        '''
        记录从0开始到某元素的最大值
        '''
        first = self.nums[0]
        max_v, self.forward_local_max[0], self.forward_global_max[0]= first, first, first
        min_v, self.forward_local_min[0], self.forward_global_min[0]= first, first, first

        for i, v in enumerate(self.nums[1:], 1):
            new_v = self.forward_local_max[i-1] + v
            self.forward_local_max[i] = max(v, new_v)
            max_v = max(max_v, self.forward_local_max[i])
            self.forward_global_max[i] = max_v

            new_v = self.forward_local_min[i-1] + v
            self.forward_local_min[i] = min(v, new_v)
            min_v = min(min_v, self.forward_local_min[i])
            self.forward_global_min[i] = min_v

    def make_reverse(self):

        last = self.nums[-1]
        max_v, self.inverse_local_max[-1], self.inverse_global_max[-1]= last, last, last
        min_v, self.inverse_local_min[-1], self.inverse_global_min[-1]= last, last, last

        for i, v in reversed(list(enumerate(self.nums[0:-1]))):
            new_v = self.inverse_local_max[i+1] + v
            self.inverse_local_max[i] = max(v, new_v)
            max_v = max(max_v, self.inverse_local_max[i])
            self.inverse_global_max[i] = max_v

            new_v = self.inverse_local_min[i+1] + v
            self.inverse_local_min[i] = min(v, new_v)
            min_v = min(min_v, self.inverse_local_min[i])
            self.inverse_global_min[i] = min_v

    # def make_forward_min(self):
    #     '''
    #     记录从0开始到某元素的最大值
    #     '''
    #     first = self.nums[0]
    #     min_v, self.forward_local_min[0], self.forward_global_min[0]= first, first, first

    #     for i, v in enumerate(self.nums[1:], 1):
    #         new_v = self.forward_local_min[i-1] + v
    #         self.forward_local_min[i] = min(v, new_v)

    #         min_v = min(min_v, self.forward_local_min[i])
    #         self.forward_global_min[i] = min_v

    # def make_reverse_min(self):

    #     last = self.nums[-1]
    #     min_v, self.inverse_local_min[-1], self.inverse_global_min[-1]= last, last, last
    #     # print(min_v)

    #     for i, v in reversed(list(enumerate(self.nums[0:-1]))):
    #         new_v = self.inverse_local_min[i+1] + v
    #         self.inverse_local_min[i] = min(v, new_v)

    #         min_v = min(min_v, self.inverse_local_min[i])
    #         self.inverse_global_min[i] = min_v

    def tow_max(self):
        m = -999999999
        for i in range(self.n-1):
            m1 = self.forward_global_max[i] - self.inverse_global_min[i+1]
            m2 = self.inverse_global_max[i+1] - self.forward_global_min[i]
            m = max(m, m1, m2)

        return m


def main():
    # print("start main")

    l = [1, 2, -3, 1]
    s = Solution()
    ret = s.maxDiffSubArrays(l)
    print(s.forward_global_max)
    print(s.inverse_global_min)
    print(ret)

if __name__ == "__main__":
    main()
